package 二分查找;

import java.util.Arrays;

public class 最长上升子序列 {
    // 令人震惊的二分法（标准写法）
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            // [4 6 10] 找2，返回-1， 第一个比2大的数是4，下标为0
            int i = Arrays.binarySearch(dp, 0, len, num);//返回值为负的插入点值，所谓插入点值就是第一个比关键字大的元素在数组中的位置索引，而且这个位置索引从1开始。
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

    //  真二分写法(low + high) >>> 1;
    public int lengthOfLIS2(int[] nums) {

        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int left = 0, right = len;
            // 二分查找插入位置
            while (left < right) {
                int mid = (left + right) >>> 1;//无符号右移,高位补0，就是说越界也能挪回来
                if (dp[mid] >= num) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[left] = num;
            if (left == len) {
                len++;
            }
        }
        // 牌堆数就是 LIS 长度
        return len;
    }

}
